/*
 * graphFunctions.c
 *
 *  Created on: 01/06/2011
 *      Author: Jonatas Lopes de Paiva
 *
 *  Implementa graphFunctions.h e mais algumas funcoes auxiliares.
 */

#include "graphFunctions.h"

/*
 * Cria o grafo
 * */
Grafo *criaGrafo() {
	Grafo *grafo = (Grafo*) malloc(sizeof(Grafo));
	grafo->head = NULL;
	grafo->size = 0;

	return grafo;
}

/*
 * Funcao auxiliar que cria um vertice
 * */
Vertice *criaVertice(int rotulo, Vertice *prox) {
	Vertice *vertice = (Vertice*) malloc(sizeof(Vertice));
	vertice->rotulo = rotulo;
	vertice->headArestas = NULL;
	vertice->size = 0;
	vertice->prox = prox;

	return vertice;
}

/*
 * Funcao auxiliar que insere um vertice caso ele nao exista.
 * Caso ele exista ela simplesmente retorna o vertice.
 *
 * O vertice sempre e inserido em ordem crescente de rotulo.
 * */
Vertice *insereVertice(int rotulo, Grafo *grafo) {

	/*
	 * Grafo vazio ou e inserido na primeira posicao
	 * */
	if ((grafo->size == 0) || (grafo->head->rotulo > rotulo)) {
		Vertice *vertice = criaVertice(rotulo, grafo->head);
		grafo->head = vertice;
		grafo->size++;
		return vertice;
	}

	Vertice *it = grafo->head;
	int i = 0;

	/*
	 * Busca o elemento e insere no lugar correto caso nao ache o elemento.
	 * */
	for (i = 0; i < grafo->size; i++) {
		if (it->rotulo == rotulo) {
			return it;
		}

		if ((it->prox == NULL) || (it->prox->rotulo > rotulo)) {
			Vertice *vertice = criaVertice(rotulo, it->prox);
			it->prox = vertice;
			grafo->size++;
			return vertice;
		}

		it = it->prox;
	}

	return NULL;

}

/*
 * Funcao auxiliar que cria uma aresta
 * */
Aresta *criaAresta(int custo, Aresta *prox, Vertice *destino) {
	Aresta *aresta = (Aresta*) malloc(sizeof(Aresta));
	aresta->custo = custo;
	aresta->destino = destino;
	aresta->prox = prox;
	return aresta;
}

/*
 * Funcao auxiliar que insere uma Aresta entre dois vertices.
 *
 * A aresta tambem e inserida em ordem crescente de custo.
 *
 * Caso ja exista aresta entre os dois vertices a funcao retorna 0.
 * */
int insere(Vertice *origem, Vertice *destino, int custo, Grafo *grafo) {

	/*
	 * Nenhuma aresta neste vertice.
	 * */
	if (origem->size == 0) {
		Aresta *aresta = criaAresta(custo, NULL, destino);
		origem->headArestas = aresta;
		origem->size++;
		return 1;
	}

	Aresta *it = origem->headArestas;
	int i = 0;

	/*
	 * Verifica se ja existe aresta
	 * */
	for (i = 0; i < origem->size; i++, it = it->prox) {
		if (it->destino == destino) {
			return 0;
		}
	}

	Aresta *aresta = criaAresta(custo, NULL, destino);

	/*
	 * Insere a aresta
	 * */
	if (custo < origem->headArestas->custo) {
		aresta->prox = origem->headArestas;
		origem->headArestas = aresta;
	} else {
		it = origem->headArestas;

		for (i = 0; i < origem->size; i++) {
			if ((it->prox == NULL) || (it->prox->custo > custo)) {
				aresta->prox = it->prox;
				it->prox = aresta;
				break;
			}
			it = it->prox;
		}

	}

	origem->size++;
	return 1;
}

/*
 * Insere aresta.
 * */
int insereAresta(int rotuloOrigem, int rotuloDestino, int custo, Grafo *grafo) {

	Vertice *origem = insereVertice(rotuloOrigem, grafo);
	Vertice *destino = insereVertice(rotuloDestino, grafo);

	return insere(origem, destino, custo, grafo);

}

/*
 * Funcao auxiliar que apaga todas as arestas de um Vertice
 * */
void destroyArestas(Vertice *vertice) {
	Aresta *it = vertice->headArestas;
	vertice->headArestas = NULL;

	int i = 0;

	for (i = 0; i < vertice->size; i++) {
		Aresta *aux = it;
		it = it->prox;
		free(aux);
	}

}

/*
 * Apaga todos os vertices de um grafo e apaga o grafo em seguida
 * */
void destroyGrafo(Grafo *grafo) {

	Vertice *it = grafo->head;
	grafo->head = NULL;

	int i = 0;

	for (i = 0; i < grafo->size; i++) {
		Vertice *aux = it;
		it = it->prox;
		destroyArestas(aux);

		free(aux);
	}

	free(grafo);

}
